// 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

// struct Node {
//   int val;
//   Node *left;
//   Node *right;
//   Node *next;
// }
// 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

// 初始状态下，所有 next 指针都被设置为 NULL。


/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

// ===============================递归解法：前序遍历框架===============================
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  // 空树容错
  if(!root) return root;
  // 连接相邻节点的函数
  let connectNode = function (node1, node2) {
      if (!node1 || !node2) return;
      // 连接这两个相邻节点
      node1.next = node2;
      // 递归连接node1的左右子节点
      connectNode(node1.left, node1.right);
      // 递归连接node2的左右子节点
      connectNode(node2.left, node2.right);
      // 递归连接node1的左子节点和node2的右节点
      connectNode(node1.right, node2.left);
  }
  connectNode(root.left, root.right);
  return root
};


// ===============================BFS层序遍历框架===============================
/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  if (!root) return root;
  let queue = [];
  queue.push(root);
  while (queue.length !== 0) {
      let size = queue.length;
      // 记录队头
      let qHead = queue[0];
      let p = qHead;
      // 连接这一层的所有元素
      for (let step = 0; step <= size - 1; step++) {
          let outOne = queue.shift();
          // 连接操作（类似链表）
          if (outOne !== qHead) {
              p.next = outOne;
              p = p.next;
          }
          // 子元素入队
          if (outOne.left !== null) {
              queue.push(outOne.left);
          }
          if (outOne.right !== null) {
              queue.push(outOne.right);
          }
      }
  }
  return root
};